# -*- coding: utf-8 -*-


class Heap():
    __maxSize = 100

    def __init__(self):
        self.items = []

    def insert(self, key, data):
        item = HeapItem(key, data)
        self.items.append(item)
        index = len(self.items) - 1
        self.__heapify_up(index)

    def change_key(self, index, key):
        self.items[index].key = key
        self.__heapify(index)

    def change_data(self, index, data):
        self.items[index].data = data
        self.__heapify(index)

    def extract_min(self):
        min = self.items[0]
        self.__delete(0)

        return min.data

    def empty(self):
        return self.__length() == 0

    def __delete(self, index):
        item = self.items.pop()
        if index < self.__length():
            self.items[index] = item
            self.__heapify(index)

    def __heapify(self, index):
        parent = self.__parent(index)

        if self.items[index].key < self.items[parent].key:
            self.__heapify_up(index)
        else:
            self.__heapify_down(index)

    def __heapify_up(self, index):
        if index > 0:
            parent = self.__parent(index)
            if self.items[index].key < self.items[parent].key:
                self.__swap(index, parent)
                self.__heapify_up(parent)

    def __heapify_down(self, index):
        length = self.__length()

        left = self.__left(index)
        right = self.__right(index)
        #Verify if current has children
        if left >= length:
            return
        #Verify if current has right child
        elif right < length:
            leftChild = self.items[left]
            rightChild = self.items[right]

            if leftChild.key < rightChild.key:
                min = left
            else:
                min = right
        #Then only left child exists
        elif left == length - 1:
            min = left
        else:
            raise Exception('There something wrong!')

        item = self.items[index]
        child = self.items[min]

        if child.key < item.key:
            self.__swap(index, min)
            self.__heapify_down(min)

    def __swap(self, i, j):
        "Swaps nodes in the heap"
        temp = self.items[i]
        self.items[i] = self.items[j]
        self.items[j] = temp

    def __length(self):
        "Returns the number of elements in the heap"
        return len(self.items)

    def __item(self, index):
        item = None
        if index < self.__length():
            item = self.items[index]
        return item

    def __left(self, index):
        return (2 * index) + 1

    def __right(self, index):
        return (2 * index) + 2

    def __parent(self, index):
        if index == 0:
            return 0
        elif index % 2 == 0:
            return index / 2 - 1
        else:
            return index / 2

    def size(self):
        return self.__length()

    def show(self):
        for index in range(self.__length()):
            item = self.__item(index)
            left = self.__item(self.__left(index))
            right = self.__item(self.__right(index))
            output = str(item.key)
            if left is not None:
                output += ' (left=' + str(left.key) + ')'
            if right is not None:
                output += ' (right=' + str(right.key) + ')'

            print output
        print '---------------------------'


class HeapItem():

    def __init__(self, key, data):
        self.key = key
        self.data = data
